#include "util.h"
#include "table-structures.h"

#ifndef __BITARRAY_H_
#define __BITARRAY_H_

// a bit array which allows overlays

struct BitArray {
  BitArray() : block_(NULL, 0), overlay_(NULL), base_(NULL) {}
  ~BitArray() { delete [] block_.data_; }
  
  void Init(uint64 size, uint64 init_pattern = 0); // create from scratch
  void Store(string fn);
  void Load(string fn);

  void Commit(); // commit overlay to base.

  void AddBase(BitArray *base, Table<uint64> *t);

  bool Get(uint64 i);
  void Set(uint64 i, bool val);
  void OrEqRange(uint64 start, uint64 length, uint64 bits);
  uint64 GetRange(uint64 start, uint64 length);
  void Toggle(uint64 i) {Set(i, !Get(i)); }

  // for internal use
  uint64 ReadableWord(uint64 i);
  uint64 * WritableWordPointer(uint64 i);

  // Number of bits of data (not including preamble)
  uint64& Size();
  
  // Number of 64bit words of data (not including preamble)
  static uint64 SizeToWordSize(uint64 size) { return CeilingDiv(size, 64); }
  uint64 WordSize() { return SizeToWordSize(Size()); }
  uint64 * Data() { return ((uint64*)block_.data_) + 1; }
  Memblock block_;
  
  // not owned, but do not use the same table for two BitArrays
  Table<uint64> *overlay_;  
  BitArray *base_;
};

struct SimpleBitArray {
  SimpleBitArray() : block_(NULL, 0) {}
  ~SimpleBitArray() { delete [] block_.data_; }
  
  void Init(uint64 size); // create from scratch
  void ZeroOut();
  void Store(string fn);
  void Load(string fn);

  bool Get(uint64 i) {
    return data_[i >> 6] & (1ull << (i & 0x3F)); }

  void Set(uint64 i, bool val) {
    uint64 *wp = data_ + (i >> 6);
    uint64 bit = (1ull << (i & 0x3f));
    uint64 vbit = val ? bit : 0;
    *wp = vbit | (*wp & ~bit); 
  }

  void PrepareToBuild() { Size() = 0; }
  void Push(bool val) {
    Set(Size(), val);
    Size()++;
  }

  void SetRange(uint64 start, uint64 length, uint64 bits) {
    uint64 w = start >> 6;
    uint64 p = start & 0x3F;
    // TODO: make faster
    SetBits(data_ + w, bits, p, length);
    if (p + length > 64) {
      SetBits(data_+w+1, (bits >> (64-p)), 0, length - (64 - p));
    }
    //cout << "SetRange " << start << " " << length << " " << bits << " w= " << w 
    //	 << " p=" << p << " data_[w]= " << data_[w] << endl;    
  }
  void PushRange(uint64 length, uint64 bits) {
    // cout << "PushRange " << length << " " << bits << endl;
    SetRange(Size() , length, bits);
    Size() += length;
    // for (uint64 i=0; i<Size(); i++) cout << (Get(i) ? 1 : 0);
    // cout << endl;
    CHECK(GetRange(Size()-length, length) == bits);
  }
  
  void OrEqRange(uint64 start, uint64 length, uint64 bits) {
    uint64 w = start >> 6;
    uint64 p = start & 0x3F;
    // TODO: make faster
    data_[w] |= bits << p;
    if (p + length > 64)
      data_[w+1] |= bits >> (64 - p);
  }
  // bit 0 is the most significant bit. 
  uint64 GetRange(uint64 start, uint64 length) {    
    uint64 w = start >> 6;
    uint64 p = start & 0x3F;
    uint64 ret = 
      (
       (data_[w] >> p) 
       + ( (p + length > 64) ? (data_[w + 1] << (64-p)) : 0)
       ) & ((1ull << length) - 1);
    // cout << "GetRange " << start << " " << length << " -> " << ret << endl;
    return ret;
  }
  
  void Toggle(uint64 i) {Set(i, !Get(i)); }
  
  // Number of bits of data (not including preamble)
  uint64& Size() {
    return ((uint64 *)block_.data_)[0]; }  
 
  // Number of 64bit words of data (not including preamble)
  static uint64 SizeToWordSize(uint64 size) { return CeilingDiv(size, 64); }
  uint64 WordSize() { return SizeToWordSize(Size()); }
  uint64 * Data() { return ((uint64*)block_.data_) + 1; }
  Memblock block_;
  
  // not owned, but do not use the same table for two SimpleBitArrays
  uint64 *data_;
};

#endif
